#define _CRT_SECURE_NO_WARNINGS  1
//一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
//一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考
//合并链表（带哨兵位）
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //判断list1 listen 为空时
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
    if (list1)
    {
        tail->next = list1;
    }
    if (list2)
    {
        tail->next = list2;
    }
    struct ListNode* del = head;
    head = head->next;
    free(del);
    return head;
}
//反转链表
truct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while (cur)
    {
        //保存下一个节点
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}
//分割链表
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* ghead, * gtail, * lhead, * ltail;
        ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                ltail->next = cur;
                ltail = ltail->next;
            }
            else {
                gtail->next = cur;
                gtail = gtail->next;
            }
            cur = cur->next;
        }
        ltail->next = ghead->next;
        //不空可能导致环
        gtail->next = NULL;

        struct ListNode* head = lhead->next;
        free(lhead);
        free(ghead);
        return head;

    }
};